This invention relates generally to computer system security and more particularly to user authentication.
The wide availability of computers and the corresponding access to computer systems has enabled users access to a large amount of stored information. Through the use of networked computer system capabilities, a user in one location is able to gain access to data stored on a computer system residing in a remote location. To gain access to this information, the user typically sends an identifying message to attempt to gain access to a target computer system. The target computer system checks the message and determines whether the user is authorized to gain access. If the message contains the appropriate information, access is authorized; if the message does not contain the appropriate information, access is denied. This arrangement is known as user authentication. It is a process employed by a computer system by which the computer system may verify the identity of a potential user. It should be noted that although a user is typically a human being, there are instances where the user seeking verification may be another computer.
To implement an authentication system, an administrator of a computer system establishes an account on the system for a prospective user. Typically, this involves adding an entry in a database which will include identifying information about the prospective user, such as a username, and a corresponding password. The user is expected to change the password to something known only to the user after gaining access to the computer system for the first time. Each time the password is changed by the user, the database entry corresponding to that user is updated to reflect the change.
In a typical arrangement, the computer system compares the information included in the identifying message sent by the user to the information stored in the database. If the database entry corresponding to the username supplied by the potential user contains the password which was also provided by the user then access to the computer system is granted. If the password contained in the database entry corresponding to the username provided by the potential user is not the same as the password which was provided by the user, access is denied.
Using the authentication system described above, two basic problems become apparent when considering the security of the system. First of all, an intruder to the system might gain access to the database and determine the passwords for all users of the system. This enables the intruder to masquerade as an authorized user of the system at a later date using the acquired passwords.
The second problem arises when the communication between the computer system and an authorized user wishing to gain access to the computer system is intercepted or eavesdropped on by an intruder. This allows the eavesdropper to determine the authorized user's password which can be used at a later date by the eavesdropper to gain access to the system by posing as the authorized user.
It is thus desirable to provide an authentication system which provides authorized users access to the computer system. Further, the authentication system should also prevent an intruder from obtaining information which would permit the intruder to impersonate an authorized user.
Cryptography is a popular approach used in the effort to provide an optimal authentication system. A cryptographic transformation function takes a message in its original form, known as plaintext, and performs mathematical manipulations on the numerical representation of the message, transforming the message into ciphertext. Ciphertext is a representation of the original message which is unreadable, typically appearing as garbled text. Three types of cryptographic transformation functions which are used to convert plaintext to ciphertext are: secret key functions, public key functions, and hash functions. A secret key function is probably the most intuitive of the three functions and will be described first.
Secret key functions employ bidirectional encryption algorithms. A user selects a secret key which, along with the message to be encrypted, are the inputs to an algorithm. The resulting ciphertext is sent to a recipient where the recipient may be a person or a computer. To read the encrypted message, the recipient must know the user's secret key. Using the user's secret key and the ciphertext as inputs to the same algorithm used to encrypt the message, the recipient is able to decrypt the message into plaintext and thus read the message sent by the user.
Encryption may also be accomplished by using a public key function. A public key function requires two keys, a public key and a private key for each user of the system. The public key for an individual user may be known by all other users of the system. The private key for the individual user should be known only by the individual user.
For user A to send an encrypted message to user B in a public key system, user A must know user B's public key. User A encrypts a message but only those knowing user B's private key may decrypt the message.
One problem with public key cryptography is that most public key algorithms are computationally intensive. That is, they require a lot of processing time to implement and are often slow as a result.
The final method employed to encrypt messages uses hash functions. Hash functions, unlike secret key and public key functions, are one-way encryption algorithms. A hash function takes a message as input and transforms it into a fixed length number. As an example of a hash function, the numerical equivalent of message M is added to a large constant value, squared and divided by a second large constant value where the remainder is used as the hash. In this way, it would be impossible for the process to be reversed such that message M may be determined from the hash. Moreover, it can be seen that several messages may hash to the same value.
Because there is no way in which the transformation may be reversed, hash functions are typically used where a user is simply proving its knowledge of something such as a password, which the receiver also knows. The user applies a hash function to the password and sends the result to the recipient. The recipient either has the hash of the password stored with which to compare or, the recipient also applies the hash function to the password it is expecting to receive and simply compares the result to the hash of the password sent by the user. In this way knowledge of a secret (password) may be shown by the user to the recipient.
In the prior art, there are three commonly used authentication mechanisms based on secret key cryptography and hash functions: We will refer to these as "challenge/response", "storing a hashed password", and "Lamport's Hash". Each of these gives a partial solution of protecting against eavesdropping and revealing the servers database, but none gives as complete a solution as the present invention. Complete solutions using public key cryptography are well known.
In a challenge/response scheme, the server holds the password or some transformed version of the password in its database. When a user wishes to authenticate, the server chooses a nonce (a number it will never pick again, such as the current time or a large random number) and sends it to the user. The user cryptographically combines the nonce and the password and returns the result to the server. The server duplicates the user's calculation and if it gets the same answer it assumes the user must know the password. This scheme is secure against eavesdropping, but if anyone can read the server's database, they can impersonate the user.
In a "hashed password" scheme, the server holds not the password but a cryptographically transformed one-way hash of the password. To authenticate, the user sends the server the password, which the server transforms and compares to its stored copy. If they match, it assumes the password is correct. This scheme is secure against someone reading the server's database, but if anyone eavesdrops on an authentication, they can impersonate the user by replaying the authentication message.
In the "Lamport Hash" scheme, the server holds data derived from the password by iteratively one way transforming it a large number of times, say 100. It also holds the number of transformations(n). When a user wishes to authenticate, the server sends the user n. The user then transforms the password n-1 times and sends the result to the server. The server transforms the received data once and compares the result to its stored copy. If they match, it assumes the user knows the password. Further, it updates its database to contain n-1 instead of n and the new value the user sent. This scheme is secure against both eavesdropping and disclosure of the server database, but requires a periodic out-of-band resetting of the user's password when n reaches one.